package algorithm.leetcode;

import java.util.*;

public class NO438_找到字符串中所有字母异位词 {
    public static void main(String[] args) {
        System.out.println(new Solution().findAnagrams("baa", "aa"));
    }

    static class Solution {
        public List<Integer> findAnagrams(String a, String p) {
            List<Integer> answer = new ArrayList<>();

            if (a.length() < p.length()) {
                return answer;
            }

            int[] dest = new int[26];
            int[] origin = new int[26];

            for (char ch : p.toCharArray()) {
                dest[ch - 'a']++;
            }

            for (int i = 0; i < p.length(); i++) {
                origin[a.charAt(i) - 'a']++;
            }

            if (isAnagram(origin, dest)) {
                answer.add(0);
            }

            for (int i = p.length(); i < a.length(); i++) {
                origin[a.charAt(i) - 'a']++;
                origin[a.charAt(i - p.length()) - 'a']--;

                if (isAnagram(origin, dest)) {
                    answer.add(i - p.length() + 1);
                }
            }
            return answer;
        }

        private boolean isAnagram(int[] origin, int[] dest) {
            for (int i = 0; i < origin.length; i++) {
                if (origin[i] != dest[i]) {
                    return false;
                }
            }
            return true;
        }
    }
}
